{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Eventual Safe States"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #topological-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #拓扑排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: eventualSafeNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到最终的安全状态"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个有 <code>n</code> 个节点的有向图，节点按 <code>0</code> 到 <code>n - 1</code> 编号。图由一个 <strong>索引从 0 开始</strong> 的 2D 整数数组&nbsp;<code>graph</code>表示，&nbsp;<code>graph[i]</code>是与节点 <code>i</code> 相邻的节点的整数数组，这意味着从节点 <code>i</code> 到&nbsp;<code>graph[i]</code>中的每个节点都有一条边。</p>\n",
    "\n",
    "<p>如果一个节点没有连出的有向边，则该节点是 <strong>终端节点</strong> 。如果从该节点开始的所有可能路径都通向 <strong>终端节点</strong> ，则该节点为 <strong>安全节点</strong> 。</p>\n",
    "\n",
    "<p>返回一个由图中所有 <strong>安全节点</strong> 组成的数组作为答案。答案数组中的元素应当按 <strong>升序</strong> 排列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"Illustration of graph\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/03/17/picture1.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[1,2],[2,3],[5],[0],[5],[],[]]\n",
    "<strong>输出：</strong>[2,4,5,6]\n",
    "<strong>解释：</strong>示意图如上。\n",
    "节点 5 和节点 6 是终端节点，因为它们都没有出边。\n",
    "从节点 2、4、5 和 6 开始的所有路径都指向节点 5 或 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]\n",
    "<strong>输出：</strong>[4]\n",
    "<strong>解释:</strong>\n",
    "只有节点 4 是终端节点，从节点 4 开始的所有路径都通向节点 4 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == graph.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= graph[i].length &lt;= n</code></li>\n",
    "\t<li><code>0 &lt;= graph[i][j] &lt;= n - 1</code></li>\n",
    "\t<li><code>graph[i]</code> 按严格递增顺序排列。</li>\n",
    "\t<li>图中可能包含自环。</li>\n",
    "\t<li>图中边的数目在范围 <code>[1, 4 * 10<sup>4</sup>]</code> 内。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-eventual-safe-states](https://leetcode.cn/problems/find-eventual-safe-states/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-eventual-safe-states](https://leetcode.cn/problems/find-eventual-safe-states/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[2,3],[5],[0],[5],[],[]]', '[[1,2,3,4],[1,2],[3,4],[0,4],[]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        # 若起始节点在一个环内，或者可以到达一个环，则不安全\n",
    "        # 深度优先搜索+三色标记法\n",
    "        n = len(graph)\n",
    "        color = [0]*n\n",
    "        def safe(i):\n",
    "            # 该点被访问过\n",
    "            if color[i]>0:\n",
    "                return color[i]==2 \n",
    "            # 没有被访问过，先设为1\n",
    "            color[i] = 1\n",
    "            # dfs遍历下去，如果该点在环上，则一定会遍历回来\n",
    "            for j in graph[i]:\n",
    "                # 只要有一条路径有环，就不安全\n",
    "                if not safe(j):\n",
    "                    return False\n",
    "            # 没有出现环\n",
    "            color[i] = 2\n",
    "            return True            \n",
    "        return [i for i in range(n) if safe(i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        safe = []\n",
    "        color = [0] * n\n",
    "\n",
    "        def digui(x):\n",
    "            if color[x] > 0:\n",
    "                return color[x] == 2\n",
    "            color[x] = 1\n",
    "            for y in graph[x]:\n",
    "                if not digui(y):\n",
    "                    return False\n",
    "            color[x] = 2\n",
    "            return True\n",
    "        \n",
    "        return [i for i in range(n) if digui(i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        n = len(graph)\n",
    "        color = [0] * n\n",
    "        safe_nodes = []\n",
    "\n",
    "        def is_safe(node):\n",
    "            stack = [(node, iter(graph[node]))]\n",
    "\n",
    "            while stack:\n",
    "                node, neighbors = stack[-1]\n",
    "                try:\n",
    "                    neighbor = next(neighbors)\n",
    "                    if color[neighbor] == 1:\n",
    "                        return False\n",
    "                    if color[neighbor] == 0:\n",
    "                        color[neighbor] = 1\n",
    "                        stack.append((neighbor, iter(graph[neighbor])))\n",
    "                except StopIteration:\n",
    "                    color[node] = 2\n",
    "                    stack.pop()\n",
    "            return True\n",
    "\n",
    "        for i in range(n):\n",
    "            if  is_safe(i):\n",
    "                safe_nodes.append(i)\n",
    "\n",
    "        return safe_nodes\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        memo = [0] * n\n",
    "        \n",
    "        def safe(x: int) -> bool:\n",
    "            if memo[x] > 0:\n",
    "                return memo[x] == 2\n",
    "            \n",
    "            # mark as gray\n",
    "            memo[x] = 1\n",
    "\n",
    "            for y in graph[x]:\n",
    "                if not safe(y):\n",
    "                    return False\n",
    "            memo[x] = 2\n",
    "            return True\n",
    "\n",
    "        return [i  for i in range(n) if safe(i)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        color = [0] * n\n",
    "        \n",
    "        def safe(x):#可以直接判断这个点是不是安全点\n",
    "            #要判断一个点是不是安全点，就是看他出去后有没有环\n",
    "            if color[x] > 0:\n",
    "                return color[x] == 2\n",
    "            color[x] = 1\n",
    "            for next in graph[x]:\n",
    "                if not safe(next):\n",
    "                    return False\n",
    "            color[x] = 2\n",
    "            return True\n",
    "\n",
    "        return [i for i in range(n) if safe(i)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "dfs + 记忆化搜索\n",
    "\n",
    "用三个数表示节点的状态:\n",
    "0:  该节点没被遍历\n",
    "1:  该节点在递归队列中或在环中\n",
    "2:  该节点时安全节点\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        state = [0] * n\n",
    "\n",
    "        def dfs(node: int) -> bool:\n",
    "            # 如果该点遍历过, 返回该点是否是安全节点\n",
    "            if state[node] > 0:\n",
    "                return state[node] == 2\n",
    "            \n",
    "            state[node] = 1     # 状态变为 1\n",
    "            for y in graph[node]:\n",
    "                if not dfs(y):\n",
    "                    return False\n",
    "            \n",
    "            # 如果退出上面的循环, 说明节点是安全节点, 改变状态, 返回 True\n",
    "            state[node] = 2\n",
    "            return True\n",
    "        \n",
    "        # 因为有 state 数组记录每个节点的状态, \n",
    "        # 因此时间复杂度为 O(n + m), n 为节点个数, m 为边个数\n",
    "        return [i for i in range(n) if dfs(i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        #节点由0到n-1\n",
    "        #其实这就是一个找loop的题\n",
    "        #至于怎么找loop\n",
    "        #需要进行一些分析\n",
    "        #设置函数，来辨别当前的点是不是loop\n",
    "        #输入某个点\n",
    "        #初始化[0] * n\n",
    "        #1,表示loop或者访问过\n",
    "        #2,表示终端节点\n",
    "        n = len(graph)\n",
    "        global state\n",
    "        state = [0] * n\n",
    "        def dfs(pnt):\n",
    "            global state\n",
    "            if (state[pnt] != 0):#已经访问过了\n",
    "                return state[pnt] == 2\n",
    "            state[pnt] = 1#现在访问了\n",
    "            for i in graph[pnt]:\n",
    "                if (not dfs(i)):#如果有一个是bitch，那他也是bitch\n",
    "                    return False\n",
    "            state[pnt] = 2 #不是bitch\n",
    "            return True\n",
    "        return sorted([ i for i in range(n) if dfs(i)])\n",
    "        \n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        #copy\n",
    "        n = len(graph)\n",
    "        color = [0] * n\n",
    "\n",
    "        def safe(x):\n",
    "            if color[x]>0:\n",
    "                return color[x]==2\n",
    "            color[x] =1\n",
    "            for y in graph[x]:\n",
    "                if not safe(y):\n",
    "                    return False\n",
    "            color[x] =2\n",
    "            return True\n",
    "        return[i for i in range(n)  if safe(i)]\n",
    "\n",
    "        # #find a terminal node\n",
    "        # terminal =[]\n",
    "        # for i in range(len(graph)):\n",
    "        #     if len(graph[i])==0:\n",
    "        #         terminal.append(i)\n",
    "        # #build graph\n",
    "        # res = set()\n",
    "        # for i in terminal:\n",
    "        #     res.add(i)\n",
    "        # terminal = res#set(terminal) :: unhashable type :list\n",
    "        # ans =[]\n",
    "        # #find nodes \n",
    "        # for i in range(len(graph)):\n",
    "        #     if all(graph[i][j] in terminal for j in range(len(graph[i]))):\n",
    "        #         ans.append(i)\n",
    "        # for i in ans:\n",
    "        #     terminal.add(i)\n",
    "        # return sorted(list(terminal))\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        color = [0]*n\n",
    "\n",
    "        def safe(x):\n",
    "            if color[x] > 0 :\n",
    "                return color[x] == 2\n",
    "            color[x] = 1 \n",
    "            for y in graph[x]:\n",
    "                if not safe(y):\n",
    "                    return False\n",
    "            color[x] = 2\n",
    "            return True\n",
    "        # [[1,2],[2,3],[5],[0],[5],[],[]]\n",
    "        # [2,4,5,6]\n",
    "        rt = [i for i in range(n) if safe(i)]\n",
    "        return rt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        color = [0] * n\n",
    "\n",
    "        def safe(x: int) -> bool:\n",
    "            if color[x] > 0:\n",
    "                return color[x] == 2\n",
    "            color[x] = 1\n",
    "            for y in graph[x]:\n",
    "                if not safe(y):\n",
    "                    return False\n",
    "            color[x] = 2\n",
    "            return True\n",
    "\n",
    "        return [i for i in range(n) if safe(i)] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        color = [0] * n\n",
    "\n",
    "        def safe(x: int) -> bool:\n",
    "            if color[x] > 0:\n",
    "                return color[x] == 2\n",
    "            color[x] = 1\n",
    "            for y in graph[x]:\n",
    "                if not safe(y):\n",
    "                    return False\n",
    "            color[x] = 2\n",
    "            return True\n",
    "\n",
    "        return [i for i in range(n) if safe(i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        ans = []\n",
    "        queue = deque()\n",
    "        g = [[] for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "        for idx, i in enumerate(graph):\n",
    "            if not i:\n",
    "                queue.append(idx)\n",
    "                ans.append(idx)\n",
    "            for j in i:\n",
    "                g[j].append(idx)\n",
    "                deg[idx] += 1\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for x in g[node]:\n",
    "                deg[x] -= 1\n",
    "                if deg[x] == 0:\n",
    "                    ans.append(x)\n",
    "                    queue.append(x)\n",
    "\n",
    "        return sorted(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, g: List[List[int]]) -> List[int]:\n",
    "        n=len(g)\n",
    "        s=[0]*n\n",
    "        def wdnmd(node):\n",
    "            if s[node]>0:\n",
    "                return s[node]==2\n",
    "            s[node]=1\n",
    "            for i in g[node]:\n",
    "                if not wdnmd(i):\n",
    "                    return False\n",
    "            s[node]=2\n",
    "            return True\n",
    "        return [i for i in range(n) if wdnmd(i)]          \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        Solution 1, iteratively add save/terminal nodes in res, until the length of res dose not grow anymore. \n",
    "        O(N*E*S)\n",
    "        \"\"\"\n",
    "        # res = []\n",
    "\n",
    "        # n = len(graph)\n",
    "\n",
    "        # l = len(res)\n",
    "        # while True:\n",
    "        #     for i in range(n):\n",
    "        #         safe = True\n",
    "        #         for j in graph[i]:\n",
    "        #             if j not in res :\n",
    "        #                 save = False\n",
    "        #                 break\n",
    "        #         if safe and i not in res:\n",
    "        #             res.append(i)\n",
    "        #     if len(res) > l:\n",
    "        #         l = len(res)\n",
    "        #     else:\n",
    "        #         break\n",
    "        # return sorted(res)\n",
    "        \"\"\"\n",
    "        Solution 2, use DFS to find circles\n",
    "        All nodes in a cycle are not safe\n",
    "        \"\"\"\n",
    "        n = len(graph)\n",
    "        \n",
    "\n",
    "        # def save(x):\n",
    "        #     if color[x]>0:\n",
    "        #         return color[x] == 2\n",
    "        #     color[x] = 1\n",
    "        #     for y in graph[x]:\n",
    "        #         if not save(y):\n",
    "        #             return False\n",
    "        #     color[x] = 2\n",
    "        #     return True\n",
    "\n",
    "        def save(x):\n",
    "            s = [x]\n",
    "            color = [0] * n\n",
    "            while s:\n",
    "                cur = s[-1]\n",
    "                if color[cur] == 0:\n",
    "                    color[cur] = 1\n",
    "                    for y in graph[cur]:\n",
    "                        if color[y] == 1:\n",
    "                            return False\n",
    "                        elif color[y] == 0:\n",
    "                            s.append(y)\n",
    "                else:\n",
    "                    s.pop()\n",
    "                    color[cur] = 2\n",
    "            return True\n",
    "           \n",
    "\n",
    "\n",
    "\n",
    "        return [i for i in range(len(graph)) if save(i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        #走到了 终端节点 ，终端节点没有出度， 即 整个 图没有环上的节点是安全的。\n",
    "        n = len(graph) #一共n个数\n",
    "        visited = [0] * n\n",
    "        def dfs(i:int) -> bool:\n",
    "            if visited[i] >0:\n",
    "                return visited[i] == 2 #等于2 即为安全的 等于1 即为不安全的在环上\n",
    "                #如果遇到之前搜索过的点，如果该点是安全的那么 现在的点也是安全的，如果这个点是不安全的，那么当前的点也是不安全的\n",
    "            visited[i] = 1\n",
    "            for item in graph[i]:\n",
    "                if not dfs(item):\n",
    "                    return False\n",
    "            visited[i] = 2\n",
    "            return True\n",
    "        return [i for i in range(n) if dfs(i)]\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        ans = []\n",
    "\n",
    "        def dfs(graph: list[list[int]], start: int, visited: list[bool]) -> bool:\n",
    "            if visited[start] > 0:\n",
    "                return visited[start] == 2\n",
    "            \n",
    "            visited[start] = 1 # 在访问栈中，或者环中\n",
    "            for node in graph[start]:\n",
    "                if not dfs(graph, node, visited): \n",
    "                    return False\n",
    "            # 安全节点\n",
    "            visited[start] = 2\n",
    "            return True\n",
    "\n",
    "        visited = [0 for _ in range(n)]\n",
    "        for node in range(n):\n",
    "            if len(graph[node]) == 0:\n",
    "                ans.append(node)\n",
    "                visited[node] = 2\n",
    "                continue\n",
    "\n",
    "            if dfs(graph, node, visited):\n",
    "                ans.append(node)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "\n",
    "\n",
    "        n = len(graph)\n",
    "        color = [0] * n\n",
    "\n",
    "\n",
    "        def safe(x):\n",
    "            if color[x] > 0:\n",
    "                return color[x] == 2\n",
    "            color[x] = 1\n",
    "            for nex in graph[x]:\n",
    "                if not safe(nex):\n",
    "                    return False\n",
    "            color[x] = 2\n",
    "            return True\n",
    "\n",
    "        return [i for i in range(n) if safe(i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        color = [0] * n\n",
    "\n",
    "        def safe(x: int) -> bool:\n",
    "            if color[x] > 0:\n",
    "                return color[x] == 2\n",
    "            color[x] = 1\n",
    "            for y in graph[x]:\n",
    "                if not safe(y):\n",
    "                    return False\n",
    "            color[x] = 2\n",
    "            return True\n",
    "\n",
    "        return [i for i in range(n) if safe(i)]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        state = [0]*n\n",
    "        \n",
    "        def dfs(i):\n",
    "            if state[i]>0:\n",
    "                return state[i]==2\n",
    "            state[i]=1\n",
    "            for j in graph[i]:\n",
    "                if not dfs(j):\n",
    "                    return False\n",
    "            state[i]=2\n",
    "            return True\n",
    "        return [i for i in range(n) if dfs(i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        ans=[]\n",
    "        n=len(graph)\n",
    "        vis=[0 for i in range(n)]\n",
    "        def dfs(x):\n",
    "            for i in graph[x]:\n",
    "                if vis[i]==1:\n",
    "                    vis[x]=1\n",
    "                    return False\n",
    "                elif vis[i]==0:\n",
    "                    vis[i]=3\n",
    "                    if not dfs(i):\n",
    "                        vis[i]=1\n",
    "                        vis[x]=1\n",
    "                        return False\n",
    "                    else:\n",
    "                        vis[i]=2\n",
    "                elif vis[i]==3:\n",
    "                    vis[i]=1\n",
    "                    vis[x]=1\n",
    "                    return False\n",
    "            vis[x]=2\n",
    "            return True\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                vis[i]=3\n",
    "                if dfs(i):\n",
    "                    vis[i]=2\n",
    "                else:\n",
    "                    vis[i]=1\n",
    "        for i in range(n):\n",
    "            if vis[i]==2:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        g = [[] for _ in range(n)]\n",
    "        degs = [0 for _ in range(n)]\n",
    "        for i, edge in enumerate(graph):\n",
    "            for nv in edge:\n",
    "                g[nv].append(i)\n",
    "                degs[i] += 1\n",
    "               \n",
    "        ans = [] \n",
    "        for i in range(n):\n",
    "            if degs[i] == 0:\n",
    "                ans.append(i)\n",
    "        \n",
    "        dq = deque(ans)\n",
    "        while len(dq) > 0:\n",
    "            cv = dq.popleft()\n",
    "            for nv in g[cv]:\n",
    "                degs[nv] -= 1\n",
    "                if degs[nv] == 0:\n",
    "                    ans.append(nv)\n",
    "                    dq.append(nv)\n",
    "        \n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        >>> eventualSafeNodes([[1,2],[2,3],[5],[0],[5],[],[]])\n",
    "        [2, 4, 5, 6]\n",
    "        >>> eventualSafeNodes([[1,2,3,4],[1,2],[3,4],[0,4],[]])\n",
    "        [4]\n",
    "        \"\"\"\n",
    "        rg = [[] for _ in range(len(graph))]\n",
    "        for node, edges in enumerate(graph):\n",
    "            for e in edges:\n",
    "                rg[e].append(node)\n",
    "        in_degrees = [len(edges) for edges in graph]\n",
    "        q = [n for n in range(len(graph)) if in_degrees[n] <= 0]\n",
    "        while q:\n",
    "            n = q[0]\n",
    "            q = q[1:]\n",
    "            for e in rg[n]:\n",
    "                in_degrees[e] -= 1\n",
    "                if in_degrees[e] <= 0:\n",
    "                    q.append(e)\n",
    "        return [i for i, d in enumerate(in_degrees) if d == 0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n=len(graph)\n",
    "        out=[0]*n\n",
    "        degraph=[[]for _ in range(n)] #记录被哪些节点指过\n",
    "        for u in range(n):\n",
    "            out[u]=len(graph[u])\n",
    "            for v in graph[u]:\n",
    "                degraph[v].append(u)\n",
    "        res=[]\n",
    "        q=deque()\n",
    "        for i in range(n):\n",
    "            if out[i]==0:#安全节点\n",
    "                q.append(i)\n",
    "                res.append(i)\n",
    "        while q:\n",
    "            n=len(q)\n",
    "            for _ in range(n):\n",
    "                u=q.popleft()\n",
    "                for source in degraph[u]:\n",
    "                    out[source]-=1\n",
    "                    if out[source]==0:\n",
    "                        res.append(source)\n",
    "                        q.append(source)\n",
    "        res.sort()\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 疑似需要进行倒推\n",
    "# 终结节点没有出度，即相邻节点列表为空\n",
    "\n",
    "# 简单瞟了一眼答案，发现优化方法：\n",
    "# 将图改成反向图\n",
    "# 官方拓扑排序解法\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        # 生成同样格式的反向图\n",
    "        rg = [[] for _ in graph]\n",
    "        for x, ys in enumerate(graph):\n",
    "            for y in ys:\n",
    "                rg[y].append(x)\n",
    "        # 计算原图的出度，为0只进不出则为安全点\n",
    "        in_deg = [len(g) for g in graph]\n",
    "\n",
    "        # 相比自创答案的优化：队列结构而不是多重循环\n",
    "        # 首先找出安全点（此问题已经在自创答案中体现）\n",
    "        q = deque([i for i, d in enumerate(in_deg) if d==0])\n",
    "        while q:\n",
    "            for x in rg[q.popleft()]:\n",
    "                in_deg[x] -= 1\n",
    "                if in_deg[x] == 0:\n",
    "                    q.append(x)\n",
    "\n",
    "        return [i for i, d in enumerate(in_deg) if d == 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        color = [0] * n\n",
    "\n",
    "        def safe(x: int) -> bool:\n",
    "            if color[x] > 0:\n",
    "                return color[x] == 2\n",
    "            color[x] = 1\n",
    "            for y in graph[x]:\n",
    "                if not safe(y):\n",
    "                    return False\n",
    "            color[x] = 2\n",
    "            return True\n",
    "\n",
    "        return [i for i in range(n) if safe(i)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "class Solution:\r\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\r\n",
    "        n=len(graph)\r\n",
    "        rg=[[] for _ in range(n)]\r\n",
    "        for i,nodes in enumerate(graph):\r\n",
    "            for node in nodes:\r\n",
    "                rg[node].append(i)\r\n",
    "        in_deg=[len(nodes) for nodes in graph]\r\n",
    "        queue=deque([i for i in range(n) if in_deg[i]==0])\r\n",
    "        while queue:\r\n",
    "            node=queue.popleft()\r\n",
    "            for j in rg[node]:\r\n",
    "                in_deg[j]-=1\r\n",
    "                if in_deg[j]==0:\r\n",
    "                    queue.append(j)\r\n",
    "        return [i for i in range(n) if in_deg[i]==0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        #解题思路：\n",
    "        #若节点出度为0，则节点安全\n",
    "        #若节点的出度节点均为安全节点，该节点安全\n",
    "\n",
    "        n = len(graph)\n",
    "        rg = [[] for _ in range(n)]\n",
    "        for idx,edges in enumerate(graph):\n",
    "            for edge in edges:\n",
    "                rg[edge].append(idx) \n",
    "        out_degree = [len(i) for i in graph]\n",
    "\n",
    "        q = [i for i,d in enumerate(out_degree) if d == 0]\n",
    "        while q:\n",
    "            for x in rg[q.pop(0)]:\n",
    "                out_degree[x] -= 1\n",
    "                if out_degree[x] == 0:\n",
    "                    q.append(x)\n",
    "\n",
    "        return [i for i,d in enumerate(out_degree) if d == 0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        rg = [[] for _ in graph]\n",
    "        for x, ys in enumerate(graph):\n",
    "            for y in ys:\n",
    "                rg[y].append(x)\n",
    "        in_deg = [len(ys) for ys in graph]\n",
    "\n",
    "        q = deque([i for i, d in enumerate(in_deg) if d == 0])\n",
    "        while q:\n",
    "            for x in rg[q.popleft()]:\n",
    "                in_deg[x] -= 1\n",
    "                if in_deg[x] == 0:\n",
    "                    q.append(x)\n",
    "\n",
    "        return [i for i, d in enumerate(in_deg) if d == 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph) -> list[int]:\n",
    "        rg = [[] for _ in graph]\n",
    "        for x, ys in enumerate(graph):\n",
    "            for y in ys:\n",
    "                rg[y].append(x)\n",
    "        in_deg = [len(ys) for ys in graph]\n",
    "\n",
    "        q = deque([i for i, d in enumerate(in_deg) if d == 0])\n",
    "        while q:\n",
    "            for x in rg[q.popleft()]:\n",
    "                in_deg[x] -= 1\n",
    "                if in_deg[x] == 0:\n",
    "                    q.append(x)\n",
    "\n",
    "        return [i for i, d in enumerate(in_deg) if d == 0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        rg = [[] for _ in graph] #每个列表内存着 反向映射 把原始出度 改变为 反图的入度\n",
    "        for x,ys in enumerate(graph): #x即为原始出发节点 -> ys[y1,y2,y3]\n",
    "            for y in ys:\n",
    "                rg[y].append(x)\n",
    "        # indegree1 = [len(ys)  for ys in graph] #原图的出度，也就是返图的入度\n",
    "        indegree1 = [ 0] *len(graph)\n",
    "        for i in rg:\n",
    "            for k in i:\n",
    "                indegree1[k] +=1\n",
    "        #print(indegree1 == indegree2)\n",
    "\n",
    "        q = collections.deque([ i for i,d in enumerate(indegree1) if d ==0])#拿到 入度为0的点\n",
    "        while q:\n",
    "            for x in rg[q.popleft()]:\n",
    "                indegree1[x] -=1 \n",
    "                if indegree1[x] ==0:\n",
    "                    q.append(x)\n",
    "        \n",
    "        return [i for i,d in enumerate(indegree1) if d==0 ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        rg = [[] for _ in graph]\n",
    "        for x, ys in enumerate(graph):\n",
    "            for y in ys:\n",
    "                rg[y].append(x)\n",
    "        in_deg = [len(ys) for ys in graph]\n",
    "\n",
    "        q = deque([i for i, d in enumerate(in_deg) if d == 0])\n",
    "        while q:\n",
    "            for x in rg[q.popleft()]:\n",
    "                in_deg[x] -= 1\n",
    "                if in_deg[x] == 0:\n",
    "                    q.append(x)\n",
    "\n",
    "        return [i for i, d in enumerate(in_deg) if d == 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        in_degree: list[int] = [0] * len(graph)\n",
    "        mapping: dict[int, list[int]] = {}\n",
    "\n",
    "        for idx, nodes in enumerate(graph):\n",
    "            for node in nodes:\n",
    "                if node not in mapping:\n",
    "                    mapping[node] = [idx]\n",
    "                else:\n",
    "                    mapping[node].append(idx)\n",
    "                in_degree[idx] += 1\n",
    "\n",
    "        queue = deque()\n",
    "\n",
    "        for idx, degree in enumerate(in_degree):\n",
    "            if not degree:\n",
    "                queue.append(idx)\n",
    "\n",
    "        safe_nodes: list[int] = []\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            safe_nodes.append(node)\n",
    "\n",
    "            if node not in mapping:\n",
    "                continue\n",
    "\n",
    "            for parent_node in mapping[node]:\n",
    "                in_degree[parent_node] -= 1\n",
    "\n",
    "                if not in_degree[parent_node]:\n",
    "                    queue.append(parent_node)\n",
    "\n",
    "        return sorted(safe_nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        rg = [[] for _ in graph]\n",
    "\n",
    "        for x,ys in enumerate(graph):\n",
    "            for y in ys:\n",
    "                rg[y].append(x)\n",
    "\n",
    "        in_deg = [len(ys) for ys in graph]\n",
    "        q = deque([i for i,d in enumerate(in_deg) if d == 0])\n",
    "        while q:\n",
    "            for x in rg[q.popleft()]:\n",
    "                in_deg[x] -= 1\n",
    "                if in_deg[x] == 0:\n",
    "                    q.append(x)\n",
    "        \n",
    "        return [i for i,d in enumerate(in_deg) if d == 0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        >>> eventualSafeNodes([[1,2],[2,3],[5],[0],[5],[],[]])\n",
    "        [2, 4, 5, 6]\n",
    "        >>> eventualSafeNodes([[1,2,3,4],[1,2],[3,4],[0,4],[]])\n",
    "        [4]\n",
    "        \"\"\"\n",
    "        in_degrees = [0 for i in range(len(graph))]\n",
    "        rg = [[] for _ in range(len(graph))]\n",
    "        for node, edges in enumerate(graph):\n",
    "            for e in edges:\n",
    "                rg[e].append(node)\n",
    "                in_degrees[node] += 1\n",
    "        ret = []\n",
    "        q = [n for n in range(len(graph)) if in_degrees[n] <= 0]\n",
    "        while q:\n",
    "            n = q[0]\n",
    "            q = q[1:]\n",
    "            ret.append(n)\n",
    "            for e in rg[n]:\n",
    "                in_degrees[e] -= 1\n",
    "                if in_degrees[e] <= 0:\n",
    "                    q.append(e)\n",
    "        return list(sorted(ret))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        if n == 1: return [0]\n",
    "\n",
    "        in_degree_list = [0]*n\n",
    "        edges = defaultdict(list)\n",
    "        queue = deque()\n",
    "\n",
    "        for i, nodes in enumerate(graph):\n",
    "            in_degree_list[i] += len(nodes)\n",
    "            if not in_degree_list[i]:\n",
    "                queue.append(i)\n",
    "            else:\n",
    "                for node in nodes:\n",
    "                    edges[node].append(i)\n",
    "\n",
    "        while queue:\n",
    "            current = queue.popleft()\n",
    "            for prev in edges[current]:\n",
    "                in_degree_list[prev] -= 1\n",
    "                if not in_degree_list[prev]:\n",
    "                    queue.append(prev)\n",
    "\n",
    "        return [i for i in range(n) if not in_degree_list[i]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        degree = [0] * len(graph)\n",
    "        que = collections.deque()\n",
    "        dct = collections.defaultdict(list)\n",
    "\n",
    "        for pre, cur in enumerate(graph):\n",
    "            for node in cur:\n",
    "                dct[node].append(pre)\n",
    "            degree[pre] += len(cur)\n",
    "        \n",
    "        for i in range(len(graph)):\n",
    "            if degree[i] == 0:\n",
    "                que.append(i)\n",
    "        \n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            res.append(cur)\n",
    "            for node in dct[cur]:\n",
    "                degree[node] -= 1\n",
    "                if degree[node] == 0:\n",
    "                    que.append(node)\n",
    "        return sorted(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        #终端节点，出度为0\n",
    "        n = len(graph)\n",
    "        degree = [0]*n \n",
    "        edges = defaultdict(list)\n",
    "        queue = collections.deque()\n",
    "        for i in range(n):\n",
    "            degree[i] = len(graph[i])\n",
    "            if len(graph[i]) == 0:\n",
    "                queue.append(i)\n",
    "                continue\n",
    "            for j in graph[i]:\n",
    "                edges[j].append(i)\n",
    "        res = []\n",
    "        while queue:\n",
    "            i = queue.popleft()\n",
    "            # if degree[i] == 0:\n",
    "            res.append(i)\n",
    "            for j in edges[i]:\n",
    "                degree[j] -= 1\n",
    "                if degree[j] == 0:\n",
    "                    queue.append(j)\n",
    "        res.sort()\n",
    "        return res\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        edges = collections.defaultdict(list)\n",
    "        indegree = [0] * n\n",
    "        for i in range(n):\n",
    "            for u in graph[i]:\n",
    "                if i not in edges[u]:\n",
    "                    edges[u].append(i)\n",
    "                    indegree[i] += 1\n",
    "        q = [u for u in range(n) if indegree[u] == 0]\n",
    "        res = list()\n",
    "        while q:\n",
    "            u = q.pop(0)\n",
    "            res.append(u)\n",
    "            for v in edges[u]:\n",
    "                indegree[v] -= 1\n",
    "                if indegree[v] == 0:\n",
    "                    q.append(v)\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        reverseAdjList = collections.defaultdict(list)\n",
    "        n = len(graph)\n",
    "        out_degree = [0] * n\n",
    "        for i in range(n):\n",
    "            out_degree[i] += len(graph[i])\n",
    "            for j in graph[i]:\n",
    "                reverseAdjList[j].append(i)\n",
    "                pass\n",
    "            pass\n",
    "        q = [i for i in range(n) if out_degree[i] == 0]\n",
    "        res = []\n",
    "        while q:\n",
    "            cur = q.pop(0)\n",
    "            res.append(cur)\n",
    "            for i in reverseAdjList[cur]:\n",
    "                out_degree[i] -= 1\n",
    "                if out_degree[i] == 0:\n",
    "                    q.append(i)\n",
    "                    pass\n",
    "                pass\n",
    "        res.sort()\n",
    "        return res\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        import collections\n",
    "        rg = collections.defaultdict(list)\n",
    "        ind = [0] * len(graph)\n",
    "        for node, adjs in enumerate(graph):\n",
    "            for adj in adjs:\n",
    "                rg[adj].append(node)\n",
    "                ind[node] += 1\n",
    "        queue = collections.deque([])\n",
    "        for i in range(0, len(graph)):\n",
    "            if ind[i] == 0:\n",
    "                queue.append(i)\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop()\n",
    "                for i in rg[node]:\n",
    "                    ind[i] -= 1\n",
    "                    if ind[i] == 0:\n",
    "                        queue.append(i)\n",
    "        res = []\n",
    "        for node, num in enumerate(ind):\n",
    "            if num==0:\n",
    "                res.append(node)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "\n",
    "        outDegree = collections.defaultdict(int)\n",
    "        rGrapth = collections.defaultdict(list)\n",
    "        queue = collections.deque()\n",
    "\n",
    "        for src, dsts in enumerate(graph):\n",
    "            outDegree[src] = len(dsts)\n",
    "            if not outDegree[src]:\n",
    "                queue.append(src)\n",
    "            for dst in dsts:\n",
    "                rGrapth[dst].append(src)\n",
    "        \n",
    "        res = []\n",
    "        while queue:\n",
    "            dst = queue.popleft()\n",
    "            res.append(dst)\n",
    "\n",
    "            for src in rGrapth[dst]:\n",
    "                outDegree[src] -= 1\n",
    "                if not outDegree[src]:\n",
    "                    queue.append(src)\n",
    "        \n",
    "        return sorted(res)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\r\n",
    "        safe=set()\r\n",
    "        n=len(graph)\r\n",
    "        def is_safe(node,visited:set):\r\n",
    "            if node in safe:\r\n",
    "                return True\r\n",
    "            if node in visited:\r\n",
    "                return False\r\n",
    "            visited.add(node)\r\n",
    "            for nxt in graph[node]:\r\n",
    "                if not is_safe(nxt,visited):\r\n",
    "                    return False\r\n",
    "            safe.add(node)\r\n",
    "            return True\r\n",
    "        ret=[]\r\n",
    "        for i in range(n):\r\n",
    "            s=set()\r\n",
    "            # s.add(i)\r\n",
    "            if is_safe(i,s):\r\n",
    "                ret.append(i)\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        # terminals = []\n",
    "        # n = len(graph)\n",
    "        # ends = {}\n",
    "        # colors = [0] *n\n",
    "        # for i in range(n):\n",
    "        #     # graph[i] = set(graph[i])\n",
    "        #     if not len(graph[i]):\n",
    "        #         # terminals.append(i)\n",
    "        #         ends[i] = True\n",
    "        #     # elif i in graph[i]:\n",
    "        #     #     ends[i] = False\n",
    "        \n",
    "\n",
    "        \n",
    "        # import copy \n",
    "        # def dfs(vertex, visited):\n",
    "        #     visited[vertex] = True   \n",
    "        #     for neighbor in graph[vertex]:\n",
    "        #         if visited[neighbor]:\n",
    "        #             ends[vertex] = False\n",
    "        #         elif neighbor in ends:\n",
    "        #             # if vertex in ends:\n",
    "        #             #     ends[vertex] = ends[vertex] & ends[neighbor]\n",
    "        #             # else:\n",
    "        #             ends[vertex] = ends[neighbor]\n",
    "        #         else:\n",
    "        #             visited_copy = copy.deepcopy(visited)\n",
    "        #             dfs(neighbor, visited_copy)\n",
    "        #             # if vertex in ends:\n",
    "        #             #     ends[vertex] = ends[vertex] & ends[neighbor]\n",
    "        #             # else:\n",
    "        #             ends[vertex] = ends[neighbor]\n",
    "\n",
    "        #         if ends[vertex] == False:\n",
    "        #             return\n",
    "            \n",
    "            # if vertex not in ends:\n",
    "            #     ends[vertex] = True\n",
    "\n",
    "\n",
    "        # def dfs(vertex):\n",
    "        #     if colors[vertex] > 0:\n",
    "        #         return colors[vertex] == 2\n",
    "        #     colors[vertex] = 1\n",
    "        #     for neighbor in graph[vertex]:\n",
    "        #         if not dfs(neighbor):\n",
    "        #             return False\n",
    "                \n",
    "        #     colors[vertex] = 2\n",
    "        #     return True\n",
    "\n",
    "            \n",
    "        # out = []\n",
    "        # for i in range(n):\n",
    "        #     # if i not in ends:\n",
    "        #         # visited = [False]*n\n",
    "        #         # dfs(i,visited)\n",
    "\n",
    "\n",
    "        #     # if ends[i]:\n",
    "        #         # out.append(i)\n",
    "            \n",
    "        #     if dfs(i):\n",
    "        #         out.append(i)\n",
    "\n",
    "        # return out\n",
    "\n",
    "        #### topological sort\n",
    "        indegree = []\n",
    "        n = len(graph)\n",
    "        from collections import defaultdict\n",
    "        reverse_graph = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for node in graph[i]:\n",
    "                reverse_graph[node].append(i)\n",
    "            indegree.append(len(graph[i]))\n",
    "        \n",
    "        queue = []\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 0:\n",
    "                queue.append(i)\n",
    "        \n",
    "        while len(queue):\n",
    "            node = queue.pop()\n",
    "            for neighbor in reverse_graph[node]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if indegree[neighbor]==0:\n",
    "                    queue.append(neighbor)\n",
    "        \n",
    "        out = []\n",
    "        for i in range(n):\n",
    "            if indegree[i]==0:\n",
    "                out.append(i)\n",
    "        \n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        visited = set()\n",
    "        ans = []\n",
    "        def dfs(i):\n",
    "            if i in visited: return False\n",
    "            visited.add(i)\n",
    "            for neibor in graph[i]:\n",
    "                if not dfs(neibor): return False\n",
    "            graph[i] = []\n",
    "            visited.remove(i)\n",
    "            return True\n",
    "        for i in range(n):\n",
    "            if dfs(i): ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        graph_dict = {u: [] for u in range(len(graph))}\n",
    "\n",
    "        for u in range(len(graph)):\n",
    "            for v in graph[u]: #如果u指向v，即有<u,v> 则在v加入u表示入度\n",
    "                graph_dict[v].append(u)     # 逆序建图\n",
    "        \n",
    "        return self.topologicalSortingKahn(graph_dict)\n",
    "    \n",
    "    def topologicalSortingKahn(self, graph: dict):\n",
    "        indegrees = {u: 0 for u in graph}   # indegrees 用于记录所有节点入度\n",
    "        for u in graph:\n",
    "            for v in graph[u]:\n",
    "                indegrees[v] += 1           # 统计所有节点入度\n",
    "        \n",
    "        # 将入度为 0 的顶点存入集合 S 中\n",
    "        S = collections.deque([u for u in indegrees if indegrees[u] == 0])\n",
    "        \n",
    "        while S:\n",
    "            u = S.pop()                     # 从集合中选择一个没有前驱的顶点 0\n",
    "            for v in graph[u]:              # 遍历顶点 u 的邻接顶点 v\n",
    "                indegrees[v] -= 1           # 删除从顶点 u 出发的有向边\n",
    "                if indegrees[v] == 0:       # 如果删除该边后顶点 v 的入度变为 0\n",
    "                    S.append(v)             # 将其放入集合 S 中\n",
    "        \n",
    "        res = []                               # 如果最后入度为0则是安全节点加入\n",
    "        for u in indegrees:\n",
    "            if indegrees[u] == 0:\n",
    "                res.append(u)\n",
    "        \n",
    "        return res\n",
    "    \n",
    " \n",
    "  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "\n",
    "        outDegree = collections.defaultdict(int)\n",
    "        rGrapth = collections.defaultdict(list)\n",
    "        queue = collections.deque()\n",
    "\n",
    "        for src, dsts in enumerate(graph):\n",
    "            outDegree[src] = len(dsts)\n",
    "            if not outDegree[src]:\n",
    "                queue.append(src)\n",
    "            for dst in dsts:\n",
    "                rGrapth[dst].append(src)\n",
    "        \n",
    "        while queue:\n",
    "            dst = queue.popleft()\n",
    "\n",
    "            for src in rGrapth[dst]:\n",
    "                outDegree[src] -= 1\n",
    "                if not outDegree[src]:\n",
    "                    queue.append(src)\n",
    "        \n",
    "        return [ i for i in range(len(graph)) if not outDegree[i] ]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        edges = collections.defaultdict(list)\n",
    "        indegree = [0] * n\n",
    "        for i in range(n):\n",
    "            for u in graph[i]:\n",
    "                if i not in edges[u]:\n",
    "                    edges[u].append(i)\n",
    "                    indegree[i] += 1\n",
    "        q = [u for u in range(n) if indegree[u] == 0]\n",
    "        while q:\n",
    "            u = q.pop(0)\n",
    "            for v in edges[u]:\n",
    "                indegree[v] -= 1\n",
    "                if indegree[v] == 0:\n",
    "                    q.append(v)\n",
    "        return [i for i in range(n) if indegree[i] == 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        outdegree = collections.defaultdict(int)\n",
    "        connect = collections.defaultdict(list)\n",
    "        n = len(graph)\n",
    "        for i in range(n):\n",
    "            outdegree[i] = 0\n",
    "        for i, nums in enumerate(graph):\n",
    "            for num in nums:\n",
    "                outdegree[i] += 1\n",
    "                connect[num].append(i)\n",
    "        queue = collections.deque([k for k, v in outdegree.items() if v == 0])\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            res.append(node)\n",
    "            for nei in connect[node]:\n",
    "                outdegree[nei] -= 1\n",
    "                if outdegree[nei] == 0:\n",
    "                    queue.append(nei)\n",
    "        return sorted(res)\n",
    "\n",
    "# class Solution: # solution 2\n",
    "#     def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "#         n = len(graph)\n",
    "#         safe = {}\n",
    "#         def dfs(i):\n",
    "#             if i in safe:\n",
    "#                 return safe[i]\n",
    "#             safe[i] = False\n",
    "#             for nei in graph[i]:\n",
    "#                 if not dfs(nei):\n",
    "#                     return False\n",
    "#             safe[i] = True\n",
    "#             return True\n",
    "#         res = []\n",
    "#         for i in range(n):\n",
    "#             if dfs(i):\n",
    "#                 res.append(i)\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "\n",
    "        outDegree = collections.defaultdict(int)\n",
    "        rGrapth = collections.defaultdict(list)\n",
    "        queue = collections.deque()\n",
    "\n",
    "        for src, dsts in enumerate(graph):\n",
    "            outDegree[src] = len(dsts)\n",
    "            if not outDegree[src]:\n",
    "                queue.append(src)\n",
    "            for dst in dsts:\n",
    "                rGrapth[dst].append(src)\n",
    "        \n",
    "        res = []\n",
    "        while queue:\n",
    "            dst = queue.popleft()\n",
    "            res.append(dst)\n",
    "\n",
    "            for src in rGrapth[dst]:\n",
    "                outDegree[src] -= 1\n",
    "                if not outDegree[src]:\n",
    "                    queue.append(src)\n",
    "        \n",
    "        return sorted(res)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        outdegree = defaultdict(int)\n",
    "        releation = defaultdict(list)\n",
    "        for i in range(len(graph)):\n",
    "            for j in graph[i]:\n",
    "                outdegree[i] += 1\n",
    "                releation[j].append(i)\n",
    "        q = [x for x in range(len(graph)) if x not in outdegree]\n",
    "        tmp = []\n",
    "        res = []\n",
    "        while q:\n",
    "            v = q.pop(0)\n",
    "            res.append(v)\n",
    "            for i in releation.get(v, []):\n",
    "                outdegree[i] -= 1\n",
    "                if outdegree[i] == 0:\n",
    "                    q.append(i)\n",
    "\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 拓扑排序，graph 中包含所有顶点的有向边关系（包括无边顶点）\n",
    "    def topologicalSortingKahn(self, graph: dict):\n",
    "        indegrees = {u: 0 for u in graph}   # indegrees 用于记录所有节点入度\n",
    "        for u in graph:\n",
    "            for v in graph[u]:\n",
    "                indegrees[v] += 1           # 统计所有节点入度\n",
    "        \n",
    "        # 将入度为 0 的顶点存入集合 S 中\n",
    "        S = collections.deque([u for u in indegrees if indegrees[u] == 0])\n",
    "        \n",
    "        while S:\n",
    "            u = S.pop()                     # 从集合中选择一个没有前驱的顶点 0\n",
    "            for v in graph[u]:              # 遍历顶点 u 的邻接顶点 v\n",
    "                indegrees[v] -= 1           # 删除从顶点 u 出发的有向边\n",
    "                if indegrees[v] == 0:       # 如果删除该边后顶点 v 的入度变为 0\n",
    "                    S.append(v)             # 将其放入集合 S 中\n",
    "        \n",
    "        res = []\n",
    "        for u in indegrees:\n",
    "            if indegrees[u] == 0:\n",
    "                res.append(u)\n",
    "        \n",
    "        return res\n",
    "        \n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        graph_dict = {u: [] for u in range(len(graph))}\n",
    "\n",
    "        for u in range(len(graph)):\n",
    "            for v in graph[u]:\n",
    "                graph_dict[v].append(u)     # 逆序建图\n",
    "\n",
    "        return self.topologicalSortingKahn(graph_dict)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n=len(graph)\n",
    "        u=collections.defaultdict(list)\n",
    "        count=collections.Counter()\n",
    "        for i,x in enumerate(graph):\n",
    "            for j in x:\n",
    "                u[j].append(i)\n",
    "                count[i]+=1\n",
    "        queue=[i for i in range(n) if count[i]==0]\n",
    "        q=deque(queue)\n",
    "        while q:\n",
    "            x=q.popleft()\n",
    "            for i in u[x]:\n",
    "                count[i]-=1\n",
    "                if count[i]==0:\n",
    "                    q.append(i)\n",
    "                    queue.append(i)\n",
    "        return sorted(queue)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        length = len(graph)\n",
    "        outdegrees = [0] * length\n",
    "        g = collections.defaultdict(set)\n",
    "        for i in range(length):\n",
    "            li = graph[i]\n",
    "            outdegrees[i] = len(li)\n",
    "            for j in li:\n",
    "                g[j].add(i)\n",
    "        \n",
    "        res = []\n",
    "        stack = [i for i in range(length) if outdegrees[i] == 0]\n",
    "        while stack:\n",
    "            nstack = []\n",
    "            for node in stack:\n",
    "                bisect.insort_left(res, node)\n",
    "                for nxt in g[node]:\n",
    "                    outdegrees[nxt] -= 1 \n",
    "                    if outdegrees[nxt] == 0:\n",
    "                        nstack.append(nxt)\n",
    "            stack = nstack\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        \n",
    "        from collections import defaultdict\n",
    "        G = defaultdict(list)\n",
    "        indegre = defaultdict(int)\n",
    "\n",
    "        for i in range(n):\n",
    "            for node in graph[i]:\n",
    "                G[node].append(i)\n",
    "                indegre[i]+=1\n",
    "        \n",
    "        queue = []\n",
    "        for i in range(n):\n",
    "            if indegre[i]==0:\n",
    "                queue.append(i)\n",
    "\n",
    "        top_sort = []\n",
    "        while queue:\n",
    "            len_q = len(queue)\n",
    "            for i in range(len_q):\n",
    "                x = queue.pop(0)\n",
    "                top_sort.append(x)\n",
    "                for nei in G[x]:\n",
    "                    indegre[nei]-=1\n",
    "                    if indegre[nei]==0:\n",
    "                        queue.append(nei)\n",
    "\n",
    "        top_sort.sort()\n",
    "        return top_sort\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topologicalSorting(self, graph):\n",
    "        indegrees = {u : 0 for u in graph}\n",
    "        for u in graph:\n",
    "            for v in graph[u]:\n",
    "                indegrees[v] += 1\n",
    "        S = collections.deque([u for u in indegrees if indegrees[u] == 0])\n",
    "\n",
    "        while S:\n",
    "            u = S.pop()\n",
    "            for v in graph[u]:\n",
    "                indegrees[v] -= 1\n",
    "                if indegrees[v] == 0:\n",
    "                    S.append(v)\n",
    "\n",
    "        res = []\n",
    "        for u in indegrees:\n",
    "            if indegrees[u] == 0:\n",
    "                res.append(u)\n",
    "        return res\n",
    "\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        graph_dict = {u: [] for u in range(len(graph))}\n",
    "\n",
    "        for u in range(len(graph)):\n",
    "            for v in graph[u]:\n",
    "                graph_dict[v].append(u)\n",
    "        return self.topologicalSorting(graph_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "      n = len(graph)\n",
    "      indeg = defaultdict(int)\n",
    "      rg = defaultdict(list)\n",
    "      for node in range(n):\n",
    "        indeg[node] = 0\n",
    "        rg[node] = []\n",
    "      # populate rg\n",
    "      for node, adjs in enumerate(graph):\n",
    "        for adj in adjs:\n",
    "          rg[adj].append(node)\n",
    "      # populate indeg\n",
    "      for node, adjs in rg.items():\n",
    "        for adj in adjs:\n",
    "          indeg[adj] += 1\n",
    "      # populate queue with nodes whose indeg = 0\n",
    "      queue = deque()\n",
    "      for node, deg in indeg.items():\n",
    "        if deg == 0:\n",
    "          queue.append(node)\n",
    "      # run topological sort\n",
    "      res = []\n",
    "      while queue:\n",
    "        node = queue.popleft()\n",
    "        res.append(node)\n",
    "        for adj in rg[node]:\n",
    "          indeg[adj] -= 1\n",
    "          if indeg[adj] == 0:\n",
    "            queue.append(adj)\n",
    "      return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 拓扑排序，graph 中包含所有顶点的有向边关系（包括无边顶点）\n",
    "    def topologicalSortingKahn(self, graph: dict):\n",
    "        indegrees = {u: 0 for u in graph}   # indegrees 用于记录所有节点入度\n",
    "        for u in graph:\n",
    "            for v in graph[u]:\n",
    "                indegrees[v] += 1           # 统计所有节点入度\n",
    "        \n",
    "        # 将入度为 0 的顶点存入集合 S 中\n",
    "        S = collections.deque([u for u in indegrees if indegrees[u] == 0])\n",
    "        \n",
    "        while S:\n",
    "            u = S.pop()                     # 从集合中选择一个没有前驱的顶点 0\n",
    "            for v in graph[u]:              # 遍历顶点 u 的邻接顶点 v\n",
    "                indegrees[v] -= 1           # 删除从顶点 u 出发的有向边\n",
    "                if indegrees[v] == 0:       # 如果删除该边后顶点 v 的入度变为 0\n",
    "                    S.append(v)             # 将其放入集合 S 中\n",
    "        \n",
    "        res = []\n",
    "        for u in indegrees:\n",
    "            if indegrees[u] == 0:\n",
    "                res.append(u)\n",
    "        \n",
    "        return res\n",
    "        \n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        graph_dict = {u: [] for u in range(len(graph))}\n",
    "\n",
    "        for u in range(len(graph)):\n",
    "            for v in graph[u]:\n",
    "                graph_dict[v].append(u)     # 逆序建图\n",
    "\n",
    "        return self.topologicalSortingKahn(graph_dict)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseGraph(self, graph):\n",
    "        n = len(graph)\n",
    "        rev_graph = dict()\n",
    "        for i in range(n):\n",
    "            rev_graph[i] = []\n",
    "        indegs = dict()\n",
    "        for i in range(n):\n",
    "            indegs[i] = 0\n",
    "\n",
    "        for src, dests in enumerate(graph):\n",
    "            for dest in dests:\n",
    "                rev_graph[dest].append(src)\n",
    "                indegs[src] += 1\n",
    "        return rev_graph, indegs\n",
    "\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        # reverse edges & topological sort\n",
    "        rev_graph, indegs = self.reverseGraph(graph)\n",
    "        res = []\n",
    "        queue = collections.deque([])\n",
    "        n = len(graph)\n",
    "        for i in range(n):\n",
    "            if indegs[i] == 0:\n",
    "                queue.append(i)\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            res.append(node)\n",
    "            for nb in rev_graph[node]:\n",
    "                indegs[nb] -= 1\n",
    "                if indegs[nb] == 0:\n",
    "                    queue.append(nb)\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(node):\n",
    "            if node in visited:\n",
    "                return False\n",
    "            visited.add(node)\n",
    "            for neighbor in graph[node]:\n",
    "                if dfs(neighbor) == False:\n",
    "                    return False\n",
    "            graph[node] = []\n",
    "            visited.remove(node)\n",
    "            return True\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if dfs(i):\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        # 0 out degree: nodes whose out degree is 0\n",
    "        out_deg = [i for i in range(len(graph)) if len(graph[i]) == 0]\n",
    "        # in graph: key: cur node, value: node point to cur node\n",
    "        in_graph = {i: set() for i in range(len(graph))}\n",
    "        for i in range(len(graph)):\n",
    "            nodes = graph[i]\n",
    "            for n in nodes:\n",
    "                in_graph[n].add(i)\n",
    "        while len(out_deg) > 0:\n",
    "            node = out_deg.pop(0)\n",
    "            res.append(node)\n",
    "            in_nodes = in_graph[node]\n",
    "            for n in in_nodes:\n",
    "                graph[n].remove(node)\n",
    "                if len(graph[n]) == 0:\n",
    "                    out_deg.append(n)\n",
    "\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n=len(graph)\n",
    "  \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if len(graph[i])==0:\n",
    "                return True\n",
    "            nx=graph[i]\n",
    "            for j in nx:\n",
    "                if j not in visited:\n",
    "                    visited.add(j)\n",
    "                    if dfs(j)==False:\n",
    "                        return False\n",
    "                    visited.remove(j)\n",
    "                if j in visited:\n",
    "                    return False\n",
    "            return True\n",
    "        ans=[]\n",
    "        noc=set()\n",
    "        for i in range(n):\n",
    "            if i in noc:\n",
    "                continue\n",
    "            visited=set()\n",
    "            visited.add(i)\n",
    "            if dfs(i):\n",
    "                ans.append(i)\n",
    "            else:\n",
    "                for j in list(visited):\n",
    "                    noc.add(j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        \n",
    "        in_map = {i:[] for i in range(n)}\n",
    "        out_degree = {i:len(graph[i]) for i in range(n)}\n",
    "        queue = [i for i in range(n) if out_degree[i] == 0]\n",
    "        for i in range(len(graph)):\n",
    "            for v in graph[i]:\n",
    "                in_map[v].append(i)\n",
    "        res = []\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            res.append(cur)\n",
    "            for v in in_map[cur]:\n",
    "                out_degree[v] -= 1\n",
    "                if out_degree[v] == 0:\n",
    "                    queue.append(v)\n",
    "        return sorted(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        edges=collections.defaultdict(list)\n",
    "        n=len(graph)\n",
    "        outdeg=[0]*n\n",
    "        res=set()\n",
    "        for i in range(n):\n",
    "            for j in graph[i]:\n",
    "                edges[j].append(i)\n",
    "                outdeg[i]+=1\n",
    "        \n",
    "        q=collections.deque(i for i in range(n) if outdeg[i]==0)\n",
    "        while q:\n",
    "            u=q.popleft()\n",
    "            res.add(u)\n",
    "            for v in edges[u]:\n",
    "                outdeg[v]-=1\n",
    "                if outdeg[v]==0:\n",
    "                    q.append(v)\n",
    "                    res.add(u)\n",
    "        return sorted(list(res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        # find terminal\n",
    "        n = len(graph)\n",
    "        to_deg = [0]*n\n",
    "        edge_from = defaultdict(list)\n",
    "        for i, edges in enumerate(graph):\n",
    "            to_deg[i] = len(edges)\n",
    "            for to_node in edges:\n",
    "                edge_from[to_node].append(i)\n",
    "        dq = deque([x for x in range(n) if not to_deg[x]])\n",
    "        ans = set()\n",
    "        while dq:\n",
    "            node = dq.popleft()\n",
    "            ans.add(node)\n",
    "            for from_node in edge_from[node]:\n",
    "                to_deg[from_node] -= 1\n",
    "                if to_deg[from_node] <= 0:\n",
    "                    dq.append(from_node)\n",
    "        return [x for x in range(n) if x in ans]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        hashmap={}\n",
    "        inorder=[0 for i in range(len(graph))]\n",
    "        for i in range(len(graph)):\n",
    "            inorder[i]+=len(graph[i])\n",
    "            for out in graph[i]:\n",
    "                if not out in hashmap:\n",
    "                    hashmap[out]=[i]\n",
    "                else:\n",
    "                    hashmap[out].append(i)\n",
    "        stack=[]\n",
    "        for i in range(len(inorder)):\n",
    "            if inorder[i]==0:\n",
    "                stack.append(i)\n",
    "        res=[]\n",
    "        print(hashmap)\n",
    "        while stack:\n",
    "            cur=stack.pop()\n",
    "            res.append(cur)\n",
    "            if cur in hashmap:\n",
    "                for i in hashmap[cur]:\n",
    "                    inorder[i]-=1\n",
    "                    if inorder[i]==0:\n",
    "                        stack.append(i)\n",
    "        res.sort()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        # Construct the directed graph and calculate each node's out-degree\n",
    "        directedGraph = defaultdict(set)\n",
    "        outDegree = defaultdict(int)\n",
    "        for i in range(len(graph)):\n",
    "            outDegree[i] = len(graph[i])\n",
    "            # Note that the direction is reversed,\n",
    "            # because the directed graph is used to calculate out-degree\n",
    "            for j in graph[i]: \n",
    "                directedGraph[j].add(i)\n",
    "        \n",
    "        # Put all terminal nodes to the queue\n",
    "        queue = deque()\n",
    "        for i in range(len(graph)):\n",
    "            if outDegree[i] == 0: queue.append(i)\n",
    "\n",
    "        # Topological sort\n",
    "        safeNodes = []\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            safeNodes.append(cur)\n",
    "            for i in directedGraph[cur]:\n",
    "                outDegree[i] -= 1\n",
    "                if outDegree[i] == 0: queue.append(i)\n",
    "\n",
    "        return sorted(safeNodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        outdegree = [0] * n \n",
    "        \n",
    "        tmp = []\n",
    "        for i in range(n):\n",
    "            outdegree[i] = len(graph[i])\n",
    "            if outdegree[i] == 0:\n",
    "                tmp.append(i)\n",
    "\n",
    "        parent = collections.defaultdict(list)\n",
    "\n",
    "        for i, nxt in enumerate(graph):\n",
    "            for node in nxt:\n",
    "                parent[node].append(i)    \n",
    "\n",
    "        seen = set()\n",
    "        queue = collections.deque(tmp)\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            seen.add(node)\n",
    "            for pa in parent[node]:\n",
    "                outdegree[pa] -= 1\n",
    "                if outdegree[pa] == 0:\n",
    "                    queue.append(pa)\n",
    "        \n",
    "        return sorted(list(seen))\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n=len(graph)\n",
    "        safe=set()\n",
    "        for i in range(n):\n",
    "            if len(graph[i])==0:\n",
    "                safe.add(i)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if len(graph[i])==0:\n",
    "                return True\n",
    "            nx=graph[i]\n",
    "            for j in nx:\n",
    "                if j not in visited:\n",
    "                    visited.add(j)\n",
    "                    if dfs(j)==False:\n",
    "                        return False\n",
    "                    visited.remove(j)\n",
    "                if j in visited:\n",
    "                    return False\n",
    "            return True\n",
    "        ans=[]\n",
    "        noc=set()\n",
    "        for i in range(n):\n",
    "            visited=set()\n",
    "            visited.add(i)\n",
    "            if dfs(i):\n",
    "                ans.append(i)\n",
    "                safe.add(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        # stack = []\n",
    "        node_ins = [[] for i in range(len(graph))]\n",
    "        res = []\n",
    "        for i in range(len(graph)):\n",
    "            if len(graph[i]) == 0:\n",
    "                # stack.append(i)\n",
    "                res.append(i)\n",
    "            for node in graph[i]:\n",
    "                node_ins[node].append(i)\n",
    "            graph[i] = set(graph[i])\n",
    "        i = 0\n",
    "        while i<len(res):\n",
    "            for node_in in node_ins[res[i]]:\n",
    "                graph[node_in].remove(res[i])\n",
    "                if len(graph[node_in]) == 0:\n",
    "                    res.append(node_in)\n",
    "            i += 1\n",
    "\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        outdegrees, queue = list(), list()\n",
    "        reverse_adj = [set() for _ in range(len(graph))]\n",
    "        for i, edges in enumerate(graph):\n",
    "            for j in edges:\n",
    "                reverse_adj[j].add(i)\n",
    "            outdegrees.append(len(edges))\n",
    "            if len(edges) == 0:\n",
    "                queue.append(i)\n",
    "        while queue:\n",
    "            for inNode in reverse_adj[queue.pop()]:\n",
    "                outdegrees[inNode] -= 1\n",
    "                if outdegrees[inNode] == 0:\n",
    "                    queue.append(inNode)\n",
    "        \n",
    "        return [outNode for outNode, outdegree in enumerate(outdegrees) if outdegree == 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        in_order = [0 for _ in range(n)]\n",
    "        reverse_graph = defaultdict(list)\n",
    "\n",
    "        for i, targets in enumerate(graph):\n",
    "            for t in targets:\n",
    "                reverse_graph[t].append(i)\n",
    "                in_order[i] += 1\n",
    "\n",
    "        res = set()\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            if in_order[i] == 0:\n",
    "                q.append(i)\n",
    "        \n",
    "        while q:\n",
    "            cur = q.pop()\n",
    "            res.add(cur)\n",
    "            targets = reverse_graph[cur]\n",
    "            for t in targets:\n",
    "                in_order[t] -= 1\n",
    "                if in_order[t] == 0:\n",
    "                    q.append(t)\n",
    "        \n",
    "        return list(sorted(res))\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        memo = {}\n",
    "        vis = set()\n",
    "        n = len(graph)\n",
    "        def dfs(root):\n",
    "            if not graph[root]: return True\n",
    "            if root in memo: return memo[root]\n",
    "            if root in vis: return False\n",
    "            vis.add(root)\n",
    "            for nxt in graph[root]:\n",
    "                if not dfs(nxt):\n",
    "                    memo[root] = False\n",
    "                    return False\n",
    "            memo[root] = True\n",
    "            return True\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if dfs(i): ans.append(i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        secureNodes = set()\n",
    "        toDecideNodes = set(range(n))\n",
    "\n",
    "        while True:\n",
    "            changeNodes = set()\n",
    "            for node in toDecideNodes:\n",
    "                if graph[node] == []:\n",
    "                    changeNodes.add(node)\n",
    "                else:\n",
    "                    secure = True\n",
    "                    for j in graph[node]:\n",
    "                        if j not in secureNodes:\n",
    "                            secure = False\n",
    "                            break\n",
    "                    if secure:\n",
    "                        changeNodes.add(node)\n",
    "            if not changeNodes:\n",
    "                break\n",
    "            secureNodes = secureNodes | changeNodes\n",
    "            toDecideNodes = toDecideNodes - changeNodes\n",
    "        \n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if i in secureNodes:\n",
    "                res.append(i)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n=len(graph)\n",
    "        ru=[0]*n\n",
    "        q=deque()\n",
    "        z=[]\n",
    "        g=[set() for i in range(n)]\n",
    "        for i in range(n):\n",
    "            if not graph[i]:q.append(i)\n",
    "            else:\n",
    "                ru[i]+=len(graph[i])\n",
    "                for j in graph[i]:\n",
    "                    g[j].add(i)\n",
    "\n",
    "        while q:\n",
    "            p=q.popleft()\n",
    "            z.append(p)\n",
    "            for i in g[p]:\n",
    "                ru[i]-=1\n",
    "                if ru[i]==0:\n",
    "                    q.append(i)\n",
    "        return sorted(z)\n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        z=set()\n",
    "        n=len(graph)\n",
    "        for i in range(n):\n",
    "            if not i:\n",
    "                z.add(i)\n",
    "        def dfs(i):\n",
    "            if i in z:\n",
    "                return True\n",
    "            u[i]=1\n",
    "            for j in graph[i]:\n",
    "                if u[j]==1 or  not dfs(j):\n",
    "                    return False\n",
    "            return False\n",
    "        q=[]\n",
    "        for i in range(n):\n",
    "            if i in z:\n",
    "                q.append(i)\n",
    "            else:\n",
    "                u=[0]*n\n",
    "                if dfs(i):q.append(i)\n",
    "        return q\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        reverseGraph = {}\n",
    "        indegree = collections.Counter()\n",
    "        for i, children in enumerate(graph):\n",
    "            if len(children) == 0:\n",
    "                indegree[i] = 0\n",
    "            for child in children:\n",
    "                indegree[i] += 1\n",
    "                if child not in reverseGraph:\n",
    "                    reverseGraph[child] = set()\n",
    "                reverseGraph[child].add(i)\n",
    "        \n",
    "        queue = []\n",
    "        visited = set()\n",
    "        for i in range(len(graph)):\n",
    "            if indegree[i] == 0:\n",
    "                queue.append(i)\n",
    "                visited.add(i)\n",
    "        \n",
    "        while len(queue) > 0:\n",
    "            current = queue.pop(0)\n",
    "            if current not in reverseGraph:\n",
    "                continue\n",
    "            for child in reverseGraph[current]:\n",
    "                if child in visited:\n",
    "                    continue\n",
    "                indegree[child] -= 1\n",
    "                if indegree[child] == 0:\n",
    "                    queue.append(child)\n",
    "                    visited.add(child)\n",
    "        \n",
    "        result = list(visited)\n",
    "        result.sort()\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        n = len(graph)\n",
    "        outdeg = [0] * n\n",
    "        rg = collections.defaultdict(set)\n",
    "        for u in range(n):\n",
    "            for v in graph[u]:\n",
    "                outdeg[u] += 1\n",
    "                rg[v].add(u)\n",
    "        dq = collections.deque([u for u in range(n) if outdeg[u] == 0])\n",
    "        while dq:\n",
    "            u = dq.popleft()\n",
    "            for v in rg[u]:\n",
    "                outdeg[v] -= 1\n",
    "                if outdeg[v] == 0:\n",
    "                    dq.append(v)\n",
    "        return [u for u in range(n) if outdeg[u] == 0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(set)\n",
    "        n = len(graph)\n",
    "        pre_num = [0] * n\n",
    "        for i, adj in enumerate(graph):\n",
    "            for j in adj:\n",
    "                g[j].add(i)\n",
    "                pre_num[i] += 1\n",
    "        queue = deque([i for i in range(n) if pre_num[i] == 0]) # deque 在操作大数组时，性能比 list 好很多\n",
    "        ans = []\n",
    "        while len(queue):\n",
    "            q = queue.popleft()\n",
    "            ans.append(q)\n",
    "            for x in g[q]:\n",
    "                pre_num[x] -= 1\n",
    "                if pre_num[x] == 0:\n",
    "                    queue.append(x)\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        N = len(graph)\n",
    "        graph = [set(dests) for dests in graph]\n",
    "        rgraph = [set() for _ in range(N)]\n",
    "        stack = []\n",
    "        result = []\n",
    "        for i, dests in enumerate(graph):\n",
    "            if not dests:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                for dest in dests:\n",
    "                    rgraph[dest].add(i)\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            result.append(node)\n",
    "            for src in rgraph[node]:\n",
    "                graph[src].remove(node)\n",
    "                if not graph[src]:\n",
    "                    stack.append(src)\n",
    "        result.sort()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:\n",
    "        safe = set()\n",
    "        not_safe = set()\n",
    "\n",
    "        n = len(graph)\n",
    "\n",
    "        isVisited = defaultdict(int)\n",
    "\n",
    "        def dfs(node):\n",
    "            if node in safe or len(graph[node]) == 0:\n",
    "                return True\n",
    "            \n",
    "            if node in not_safe:\n",
    "                return False\n",
    "\n",
    "            isVisited[node] = 1\n",
    "\n",
    "            for target in graph[node]:\n",
    "                if isVisited[target] == 1 or dfs(target) == False:\n",
    "                    not_safe.add(node)\n",
    "                    return False\n",
    "\n",
    "            isVisited[node] = 0\n",
    "            safe.add(node)\n",
    "            return True\n",
    "\n",
    "        return [i for i in range(n) if dfs(i)]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
